The reliable functioning of the Internet is imperative to the national and economic security of United States, especially as the frequency and complexity of cyber-security threats are increasing significantly. The Internet consists of many core networks of different service providers (e.g., organizations such as enterprises, governments, universities and other educational institutions, etc.) connected by a communication “backbone.” An edge router, a type of networking device, is positioned at the edge of core networks, and manages communication routing between core networks over the backbone. Edge routers also provide authenticated access to their corresponding core networks. By contrast, core routers route data packets between hosts within core networks.
A networking device such as a router can be thought of as having a control plane and a data plane. As will be understood by those of ordinary skill in the relevant art, “data plane” and “control plane” are conceptual terms, used in the context of networking to describe the components that perform certain functions in a telecommunications architecture. The control plane is where the logic is executed governing decisions concerning operations such as forwarding, routing and verification. The data plane is where the actual movement of the network traffic occurs. The data plane performs the commands of the control plane. As such, these planes represent collections of functionalities, which can be instantiated as hardware, software, firmware and any combinations thereof as desired. The hardware used for the control plane could be based on general purpose computing units (e.g., CPUs), custom hardware such as FPGAs and ASICs, graphics units used as processing units, or a combination of these. Software Defined Network (SDN) is a dynamic, manageable and adaptable architectural model, which effectively decouples the network control and forwarding functions. It further provides the functionality to enable direct and remote network control while enabling the underlying infrastructure to be abstracted for applications and network services. SND devices use general purpose computing units and implement the various control plane functionality using updateable software modules.
Edge routers typically run implementations of the Border Gateway Protocol (BGP). BGP, being a scalable protocol, can also be used with other types of networking devices, such as core routers, top of the rack routers and Virtual Private Network (VPN) appliances to route a variety of data. The currently deployed version of BGP, which was last updated in 2006, does not include provisions for security features, and is vulnerable to malicious attacks targeting the control plane of the edge router. These attacks can be perpetuated in a number of ways, and could cause significant failures and instability, e.g., perpetuators can deny service, re-route traffic to malicious hosts, and expose network topologies. There have been significant efforts over the years to add robustness to BGP and to provide Best Common Practice (BCP) guidance for the same.
The Internet Engineering Taskforce (IETF) is currently developing BGPSEC (BGP with Security), which is an extension to BGP designed to provide path security for BGP route advertisements. The extension is meant to provide resiliency against route hijacks and Autonomous System (AS) path modifications. Specifically, two mechanisms are being defined: i) route-origin validation; and ii) path validation. As described in RFC 6480, the Resource Public Key Infrastructure (RPKI) provides the initial step used to validate BGP routing data. First, holders of AS number and IP address resources are issued RPKI Resource Certificates, which establish a binding between them and cryptographic keys for digital signature verification. Furthermore, a Route Origination Authorization (ROA), which is a digitally signed object, allows holders of IP address resources to authorize specific Autonomous Systems to originate routes. Edge routers (and other networking devices) running BGPSEC (sometimes referred to as BGPSEC speakers) can use ROAs to ensure that the network device which originated the received route was in fact authorized to originate that route.
Effectively, the BGPSEC router certificate binds an AS number to a public signature verification key. Thus, any BGPSEC speaker intending to send BGP update messages containing the BGPSEC Path to external (eBGP) peers must have a corresponding private key associated with an RPKI router certificate that belongs to the BGPSEC speaker's AS number. When the BGPSEC update message is originated, the BGPSEC_Path_Signatures attribute contains only a single signature. If the receiver of the update intends to propagate the update to an external peer, a new signature is added to the BGPSEC_Path_Signatures attribute, which quickly increases the size of the update messages. Since each BGP update message must be cryptographically signed and verified, BGPSEC requires real-time line-speed cryptographic operations on BGP path announcements. The global Internet BGP Routing Table is approaching 600,000 active BGP entries in the GBP Forwarding Table (FIB) and over 1.5 Million entries in the BGP Routing Table (RIB). Given this large size, as well as the strict time period for re-convergence following router reboots needed to satisfy provider-client Service Level Agreements (SLAs), this additional requirement of BGPSEC causes a major adoption challenge. Most currently deployed edge router control plane hardware simply does not have the processing power to handle BGPSEC's cryptographic-intensive computations.
As background, public key cryptography has become the de facto standard for communications over the Internet and many other forms of communications. Until recently, Internet communications have been secured by the first generation of public key cryptographic algorithms, such as RSA, developed in the 1970s. Newer techniques, such as arithmetic of elliptic curves, have been developed which offer both better performance and higher security than these first generation public key techniques. Elliptic curves offer significant benefits over existing public key algorithms, as one scales security upwards over time to meet the evolving threat posed by eavesdroppers and hackers with access to greater computing resources. For digital signatures, public key cryptography is used to authenticate the origin of data and protect the integrity of that data. For protecting both classified and unclassified National Security information, the National Security Agency (NSA) has decided to move to elliptic curve based public key cryptography. Where appropriate, NSA plans to use the elliptic curves over finite fields with large prime moduli (256, 384, and 521 bits) published by the National Institute of Standards and Technology (NIST).
More specifically, the NIST Digital Security Standard (DSS) specifies algorithms for applications requiring a digital signature (published as Federal Information Processing Standards (“FIPS”) Publication 186-4). Additionally, the hash functions to be used in the signature generation process are specified in the Secure Hash Standard (SHS), FIPS 180-4. Draft IETF “BGPSEC BGP Algorithms, Key Formats, & Signature Formats” (which is an update to RFC 6485, pending approval) specifies: i) the digital signature algorithm and parameters; ii) the hash algorithm and parameters; iii) the public and private key formats; and iv) the signature format which are used by RPKI Certification Authorities (CA) and BGPSEC speakers (i.e., edge routers). As this document summarizes this information, “The hashing algorithm used when generating certification requests and BGPSEC Update messages MUST be SHA-256 . . . . The signature algorithm used in certification requests and BGPSEC Update messages MUST be Elliptic Curve Digital Signature Algorithm (ECDSA).”
As described in NIST FIPS-186-4, in principle, a digital signature is an electronic analogue of a written signature, which can be used to provide assurance that the claimed signatory signed the information. The recipient of a signed message can use a digital signature as evidence in demonstrating to a third party that the claimed signatory in fact generated the signature (non-repudiation). A digital signature algorithm could be used to provide: data origin authentication (the assurance that the source of data is as claimed), data integrity (the assurance that data has not been altered), and non-repudiation (the assurance that an entity cannot deny previous actions or commitments).
A digital signature algorithm includes a signature generation process and a signature verification process. A signatory uses the generation process to generate a digital signature on data whereas a verifier uses the verification process to verify the authenticity of the signature. Each signatory has a public and private key and is the owner of that key pair. The key pair owner is the only entity that is authorized to use the private key to generate digital signatures. In order to prevent other entities from claiming to be the key pair owner and using the private key to generate fraudulent signatures, the private key must remain secret. The approved digital signature algorithms are designed so that the signatures cannot be forged. Ideally, a digital signature process should be existentially un-forgeable under chosen-message attack.
The public key is used in the signature verification process. While it is not required to keep the public key secret its integrity should be maintained. Any entity should be able to verify a correctly signed message using the public key.
Cryptographic hash functions are used with digital signature algorithms and keyed hash message authentications. In general terms, an n-bit cryptographic hash is defined as a primitive that generates n-bit hash values from arbitrary length messages, and must be one-way and collision resistant. In this context, one-way means that given a hash value, it will require about 2n hash computations in order to identify a message that hashes to the same value. Collision resistance stipulates that identifying any two different messages that hash to the same value would require about 2n/2 hash computations. SHA-256 is a 256-bit one-way hash algorithm, which by definition provides 128 bits of security against collision attacks. When a message less than 264 bits in length is input to SHA-256, the result is a message digest of size of 256 bits. Per FIPS 180-4, SHA-256 is deemed to be a secure hash algorithm. SHA-256 algorithm uses six logical functions each of which operate on 32 bit words, in a serial fashion that does not natively lend itself to parallelization, but scale with processor speed.
The Elliptic Curve Digital Signature Algorithm (ECDSA) is the elliptic curve analogue of the Digital Signature Algorithm (DSA). DSA was proposed by NIST in August 1991 for use in their Digital Signature Standard (DSS), and was adopted as FIPS 186 in 1993. Due to the fact that no subexponential-time algorithm is known for the elliptic curve discrete logarithm problem, it possesses a greater strength per key than DSA. Also, ECDSA signatures are substantially smaller than DSA signatures, and can be computationally faster. Specifically an ECDSA digital signature (r, s) is generated as specified below, using:                1. Domain parameters that are generated in accordance with FIPS 186-4 Section 6.1.1,        2. A private key that is generated as specified in FIPS 186-4 Section 6.2.1,        3. A per-message secret number that is generated as specified in FIPS 186-4 Section 6.3,        4. An approved hash function (such as SHA-256),        5. An approved random bit generator.        
NIST recommended curves for ECDSA are provided in Appendix D of FIPS 186-4. Three types of curves are provided:                1. Curves over prime fields, which are identified as P-xxx,        2. Curves over Binary fields, which are identified as B-xxx, and        3. Koblitz curves, which are identified as K-xxx, where xxx indicates the bit length of the field size.        
ECDSA and in general, public key signature algorithm operations, such as signature generation and verification, are compute intensive sequential operations, which require non-trivial amounts of compute cycles. Additionally, the operations must be performed so that they are Side-Channel Attack resilient, while vigilantly maintaining security of the private keys and per message random numbers. Although substantial research has shown yielded improvement of the serial performance of these operations with mathematical simplifications, pre-computations and other techniques, satisfying the convergence requirements over the considerable number of existing unique paths with two different concurrent public key signature algorithms is not feasible with simple serial compute optimizations or conventional task parallelization, even with the latest generation processors.
An ECDSA digital signature is verified using the same domain parameters and hash function that were used during signature generation, effectively by re-computing the signature. Due to the nature of the mathematical operations required for a proper ECDSA verification, its compute requirement is substantially higher than signature generation.
The BGPSEC standard stipulates up to two concurrent signature algorithms that can be used to sign path updates. One of these algorithms is defined as the ECDSA using SHA-256, and Curve P-256. The second algorithm is to be determined. Effectively, a BGPSEC router supporting both algorithms has to create two sets of unique signatures, which substantially increases the compute time required for signature generation. Furthermore, a path is deemed to be “valid” if either one of the signature sets is valid, potentially necessitating the computation of two signature validation algorithms for each path segment. Given that a path is on average composed of four segments (each with different signatures and private/public keys), typical path update verifications may require up to eight signature verification operations. Considering that presently there exist over 500,000 unique paths, several millions of concurrent cryptographic operations must be performed in a short time period to satisfy convergence requirements.
The BGPSEC protocol intends to create a secure environment with ROA and path verification, where once an edge router is authenticated, it is assumed to be acting within its design parameters. However, if one or more authentic edge routers are compromised, or their credentials are used to make rogue devices appear to be authentic, potential adversaries could devise and use attacks similar to Distributed Denial of Service to easily render other authentic edge routers ineffective by overwhelming them with repeated requests of path validation requests.
Furthermore, commercial edge routers have traditionally used relatively low compute CPUs and a small main memory footprint, in order to fulfill strict design requirements such as cost effectiveness, reliability and low power usage.
It would be desirable to address these issues.